package dataStructure;

import java.util.ArrayList;

public class BST {
    static class Node{
        private Integer data;
        private Node lchild;
        private Node rchild;
        public Node() {
            this.data = null;
            this.lchild = null;
            this.rchild = null;
        }
        public Boolean isEmpty(){
            return data == null;
        }
    }

    public Node BST_Search(Node T,Integer k){
        while (!T.isEmpty()&& !T.data.equals(k)){
            T = T.data>k?T.lchild:T.rchild;
        }
        return T;
    }

    public Boolean BST_Insert(Node T,Integer k){
        if (T.isEmpty()){
            T.data = k;
            T.lchild = new Node();
            T.rchild = new Node();
            return true;
        }else if (T.data.equals(k)){
            return false;
        }else if (T.data<k){
            return BST_Insert(T.rchild,k);
        }else {
            return BST_Insert(T.lchild,k);
        }
    }

    public void BST_Create(Node T, ArrayList<Integer> list){
        for (int i = 0; i < list.size(); i++) {
            BST_Insert(T, list.get(i));
        }
    }
}
